package Offer;

import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树中和为某一值的路径
 * 回溯
 * 先序遍历 + 路径记录
 * @author 是阿秋啊
 * @date 2022/08/10 21:32
 **/
public class num34 {
    LinkedList<List<Integer>> ret = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root,target);
        return ret;
    }
    public void recur(TreeNode root,int target) {
        if(root == null){
            return;
        }
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            ret.add(new LinkedList(path));
            path.removeLast();
            return;
        }
        recur(root.left,target);
        recur(root.right,target);
        path.removeLast();
    }
}